﻿using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Timtopia.DGMLPosterView;
using Timtopia.PowerGraphBeamSearch;
using System.Collections.Generic;
using System.Linq;

namespace HeapTests
{
    [TestClass]
    public class HeapTests
    {
        [TestMethod]
        public void TestMinHeap1()
        {
            var heap = new MinHeap<int> { 9, 8, 4, 1, 6, 2, 7, 4, 1, 2 };
            AssertMinHeap(heap);
        }
            
        [TestMethod]
        public void TestMinHeap2()
        {
            var heap = new MinHeap<int> { 7, 5, 1, 6, 3, 2, 4, 1, 2, 1, 3, 4, 7 };
            AssertMinHeap(heap);
        }

        [TestMethod]
        public void TestMaxHeap1()
        {
            var heap = new MaxHeap<int> { 1, 5, 3, 2, 7, 56, 3, 1, 23, 5, 2, 1 };
            AssertMaxHeap(heap);
        }
            
        [TestMethod]
        public void TestMaxHeap2()
        {
            var heap = new MaxHeap<int> { 2, 6, 1, 3, 56, 1, 4, 7, 8, 23, 4, 5, 7, 34, 1, 4 };
            AssertMaxHeap(heap);
        }

        [TestMethod]
        public void KSmallestQueueTest()
        {
            int k = 10, n = 100;
            var numbers = ShuffledNumbers(n);
            var q = new KSmallestQueue<int, int>(k);
            for (int i = 0; i < n; ++i)
            {
                q.InsertIfBetter(numbers[i], () => numbers[i]);
            }
            Assert.AreEqual(k, q.Count);
            for (int i = k - 1; i >= 0; i--)
            {
                int v = q.Pop().Key;
                Assert.AreEqual(i, v);
            }
        }

        private static int[] ShuffledNumbers(int n)
        {
            var numbers = Enumerable.Range(0, n).ToArray();
            Random rand = new Random();
            for (int i = 0; i < n; ++i)
            {
                int j = rand.Next(i, n);
                int t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
            return numbers;
        }

        private void AssertMinHeap(Heap<int> heap)
        {
            int u = int.MinValue;
            while (heap.Count > 0)
            {
                var v = heap.ExtractDominating();
                Assert.IsTrue(u <= v, "Expect " + u + " <= " + v);
                u = v;
            }
        }

        private void AssertMaxHeap(Heap<int> heap)
        {
            int u = int.MaxValue;
            while (heap.Count > 0)
            {
                var v = heap.ExtractDominating();
                Assert.IsTrue(u >= v, "Expect " + u + " >= " + v);
                u = v;
            }
        }
    }
}

